package base.C06_BinarySearch;

/**
 * Instruction：查找第一个值等于给定值的元素
 * 数据状况: 数组中元素不重复, 有指定元素, 返回position; 没有指定元素, 返回-1;
 * Author：@author MaLi
 */
public class Code03_FindTheFirst {
    public static int find(int[] arr, int num) {
        //有效性验证
        if (arr == null || arr.length < 1)
            return -1;
        //查找第一个给定值
        int start = 0;
        int end = arr.length - 1;
        int middle;
        while (start <= end) {
            middle = start + ((end - start) >> 1);
            if (arr[middle] == num) {
                if ((middle - 1) >= 0 && arr[middle - 1] == num) {
                    end = middle - 1; //说明当前middle值还不是end, end至少是middle-1(数组不越界的前提下)
                } else {
                    return middle;
                }
            } else if (arr[middle] > num) { //说明中间值在目标值的右边, 我们应该重新确定end值, 排除一半无用值
                end = middle - 1;
            } else {
                start = middle + 1;  //说明中间值在目标值的左边, 我们应该重新确定start值, 排除一半无用值
            }
        }
        return -1;
    }
}
